/*************************************************************************
	> File Name: 232.用栈实现队列.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 二  9/ 7 18:41:35 2021
 ************************************************************************/

//算法思想：双栈-- 输入栈(处理push) + 输出栈（处理pop和peek)
//pop时如果输出栈为空，则将输入栈的数据依次弹出并压入输出栈中；否则弹出输出栈的栈顶元素即可

typedef struct {
    int *data;
    int top;
    int capacity;
} Stack;

Stack *stackCreate(int capacity) {
    Stack *sta = malloc(sizeof(Stack));
    sta->data = malloc(sizeof(int) * capacity);
    sta->top = -1;
    sta->capacity = capacity;
    return sta;
}

void stackPush(Stack *obj, int x) {
    obj->data[++(obj->top)] = x;
}

void stackPop(Stack *obj) {
    obj->top--;   
} 

int stackTop(Stack *obj) {
    return obj->data[obj->top];
}

bool stackEmpty(Stack *obj) {
    return obj->top == -1;
}

void stackFree(Stack *obj) {
    if (obj == NULL) return ;
    free(obj->data);
    free(obj);
    return ;
}

typedef struct {
    Stack *inStack;
    Stack *outStack;
} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
    MyQueue *que = malloc(sizeof(MyQueue));
    que->inStack = stackCreate(100);
    que->outStack = stackCreate(100);
    return que;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    stackPush(obj->inStack, x);
}

void in2out(MyQueue *obj) {
    while (!stackEmpty(obj->inStack)) {
        stackPush(obj->outStack, stackTop(obj->inStack));
        stackPop(obj->inStack);
    }
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    if (stackEmpty(obj->outStack)) {
        in2out(obj);
    }
    int x = stackTop(obj->outStack);
    stackPop(obj->outStack);
    return x;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    if (stackEmpty(obj->outStack)) {
        in2out(obj);
    }
    return stackTop(obj->outStack);
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return stackEmpty(obj->inStack) && stackEmpty(obj->outStack);
}

void myQueueFree(MyQueue* obj) {
    stackFree(obj->inStack);
    stackFree(obj->outStack);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/
